#pragma once
#include "BaseSort.h"
#include <iostream>

template < class T >
class QSort : public BaseSort < T >
{
private:
    void _Sort(T* const _array, const int pos)
    {
        int lP = 0, rP = pos;
        T ptr;

        ptr = _array[pos >> 1];
        do
        {
            while (_array[lP] < ptr) ++lP;
            while (_array[rP] > ptr) --rP;

            if (lP <= rP)
            {
                T toSwap = _array[lP];
                _array[lP] = _array[rP];
                _array[rP] = toSwap;
                ++lP;
                --rP;
            }
        }
        while (lP <= rP);

        if (rP > 0) _Sort(_array, rP);
        if (lP < pos) _Sort(_array + lP, pos - lP);
    }

public:
    QSort(T* const _array, const int _len) : BaseSort(_array, _len) {};
    ~QSort(){}

    void Sort()
    {
        if (m_data && m_size > 1)
        {   
            m_lastTime = GetTickCount();

            _Sort(m_data, m_size - 1);

            m_lastTime = GetTickCount() - m_lastTime;
        }
        else
        {
            std::cout << "qsort error!!!" << std::endl;
        }
    }
};